#include <iostream>
#include <tuple>
using namespace std;

template<typename T, unsigned n>
void Merge(T(*arr)[n], size_t left, size_t r, size_t right)
{
	if (left == right)
		return;
	// create new arrays

	int lnum = r - left + 1, rnum = right - r;
	T* pLarr = new int[lnum]();//这里并没有使用哨兵
	T* pRarr = new int[rnum]();
	int i, j = 0;
	for (i = 0; i < lnum; ++i)
		pLarr[i] = (*arr)[left + i];
	for (i = 0; i < rnum; ++i)
		pRarr[i] = (*arr)[r + 1 + i];

	i = j;
	int k;
	for (k = left; k < right; ++k)
	{
		if (pLarr[i] > pRarr[j])
		{
			(*arr)[k] = pLarr[i];
			++i;
		}
		else
		{
			(*arr)[k] = pRarr[j];
			++j;
		}
	}

	for (;
		i != lnum; ++i, ++k)
		(*arr)[k] = pLarr[i];

	for (;
		j != rnum; ++j, ++k)
		(*arr)[k] = pRarr[j];

	delete[] pLarr;
	delete[] pRarr;
}

template<typename T, unsigned n>
void MergeSort(T(*arr)[n], size_t left, size_t right = n)
{
	if (left >= right)
	{
		return;
	}
	int r = (right + left) / 2;

	MergeSort(arr, left, r);
	MergeSort(arr, r + 1, right);

	Merge(arr, left, r, right);
}
////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////
//Binary Search
template<typename T, size_t n>
size_t GetArrSize(T (*arr)[n])
{
	return n;
}
template<typename T, size_t n>
int BinarySearch(T(*arr)[n], T& val, size_t low = 0, size_t right = n)//logn
 {
	if (low > right)
		return -1;
	int mid = (low + right) / 2;

	if ((*arr)[mid] < val)
		BinarySearch(arr, val, low, mid-1);
	else if ((*arr)[mid] > val)
		BinarySearch(arr, val, mid+1, right);
	else
		return mid;
}

template<typename T, size_t n>
tuple<size_t, size_t> Search(T(*arr)[n], int &s, size_t sz = n)
{
	//排序过的
	for (size_t i = 0; i < sz; ++i)
	{
		for (size_t k = i + 1; k < sz; ++i)
		{
			if ((*arr)[i] + (*arr)[k] == s)
				return tuple<size_t, size_t>(i, k);
		}
	}
	return tuple<size_t, size_t>(0, 0);
}

template<typename T, size_t n>
tuple<size_t, size_t> Search_nLogn(T(*arr)[n], int &s, size_t sz = n)
{
	int k = 0;
	//数组必须有序
	for (int i = 0; i < sz; ++i)
	{
		k = s - (*arr)[i];
		int Temp = BinarySearch(arr, k);
		if (Temp == -1)
			continue;
		else
			return tuple<size_t, size_t>(i, Temp);
	}
}

template<typename T, size_t n>//冒泡排序
void BubbleSort(T(*arr)[n], size_t sz = n)
{
 	for (int i = 0; i < sz; ++i)
	{
		for (int k = 0; k < sz; ++k)
		{
			if ((*arr)[k] < (*arr)[k + 1])
				swap((*arr)[k], (*arr)[k + 1]);
		}
	}
}

int main()
{
	int arr1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	BubbleSort(&arr1);
	//MergeSort(&arr1, 0);

	int n = 6;

	int sum = 11;
	//tuple<size_t, size_t> a = Search(&arr1, sum);
	tuple<size_t, size_t> a = Search_nLogn(&arr1, sum);
	size_t sub = BinarySearch(&arr1, n);
	
	return 0;
}
